package com.dsaa.quicksort;

import java.util.Random;

public class Quicksort {
    public static void main(String[] args) {
        Quicksort quicksort = new Quicksort();
        int[] res = quicksort.sortArray(new int[]{5, 2, 3, 1});
        System.out.println(res);
    }

    public int[] sortArray(int[] nums) {
        // 冒泡排序
        // for (int i = 0; i < nums.length; i++) {
        //     for (int j = i + 1; j < nums.length; j++) {
        //         if (nums[i] > nums[j]) {
        //             int temp = nums[i];
        //             nums[i] = nums[j];
        //             nums[j] = temp;
        //         }
        //     }
        // }
        // return nums;

        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int pos = getIndex(nums, left, right);
            quickSort(nums, left, pos - 1);
            quickSort(nums, pos + 1, right);
        }
    }

    public int getIndex(int[] nums, int left, int right) {
        // 随机选一个作为我们的主元
        int i = new Random().nextInt(right - left + 1) + left;
        swap(nums, right, i);
        return partition(nums, left, right);
    }

    public int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        int i = left - 1;
        // 这里减 1 是因为 right 在前面已经被取出了
        for (int j = left; j <= right - 1; j++) {
            if (nums[j] <= pivot) {
                i = i + 1;
                // 交换的目的是为了，将参照值小的从左到右排列
                // 如果 n 在数组中有 x 个值比 n 小，那么 n 排序后的坐标就是 x-1
                swap(nums, i, j);
            }
        }
        // 交换的目的是为了将 right 放入排序结果的坐标
        swap(nums, i + 1, right);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
